from typing import Optional
from itertools import chain
# 队列
"""
队列跟栈一样，也是一种操作受限的线性表数据结构.
先进先出，后进后出。它具有先进先出的特性，支持在队尾插入元素，在队头删除元素.
队列的概念很好理解，基本操作也很容易掌握。作为一种非常基础的数据结构，
队列跟栈非常相似，支持的操作也很有限，最基本的操作也是两个：入队 enqueue()，放一个数据到队列尾部；出队 dequeue()，从队列头部取一个元素。
队列的应用也非常广泛，特别是一些具有某些额外特性的队列，比如循环队列、阻塞队列、并发队列。
它们在很多偏底层系统、框架、中间件的开发中，起着关键性的作用。
比如高性能队列 Disruptor、Linux 环形缓存，都用到了循环并发队列；Java concurrent 并发包利用 ArrayBlockingQueue 来实现公平锁等。
跟栈一样，队列可以用数组来实现，也可以用链表来实现。用数组实现的栈叫作顺序栈，用链表实现的栈叫作链式栈。
同样，用数组实现的队列叫作顺序队列，用链表实现的队列叫作链式队列。
"""


# 队列的实现


# python 中没有数组，用列表代替数组实现时可以忽略数组固定分配空间和连续内存地址造成一些问题
class ArrayQueue(object):
    def __init__(self):
        self.items = []

    def enqueue(self, value):
        self.items.append(value)

    def dequeue(self):
        if len(self.items) > 0:
            self.items.remove(self.items[0])


# 把列表完全当成数组，提前定义数组长度，内存地址固定
class ArrayQueue2(object):
    def __init__(self, capacity: int):
        self.items = []  # 数组
        self.capacity = capacity  # 数组长度
        self.head = 0  # 队列第一个数据下标
        self.tail = 0  # 队列最后一个数据下标

    def enqueue(self, value: str) -> bool:
        if self.tail == self.capacity:
            if self.head == 0:  # 队列数据已满
                return False
            else:  # 队列数据未满，迁移数据到首位
                for v in range(0, self.tail - self.head):
                    self.items[i] = self.items[self.head + v]
                    self.tail = self.tail - self.head
                    self.head = 0
        self.items[self.tail] = value
        self.tail += 1
        return True

    def dequeue(self) -> bool:
        if self.head != self.tail:
            self.head += 1
            return True
        else:
            return False

    def __repr__(self):
        return " ".join(self.items[self.head:self.tail])


# 用链表来实现队列
class Node(object):
    def __init__(self, value: str, next_node=None):
        self.data = value
        self.next = next_node


class LinkedQueue(object):
    def __init__(self):
        self.head = None
        self.tail = None

    def enqueue(self, value: str):
        new_node = Node(value)
        if self.tail:
            self.tail.next = new_node
        else:
            self.head = new_node
        self.tail = new_node

    def dequeue(self):
        if self.head:
            self.head = self.head.next

    def __repr__(self):
        values = []
        p = self.head
        while p:
            values.append(p.data)
            p = p.next
        return "->".join(values)


# 基于数组实现循环队列
class CircularQueue(object):
    def __init__(self, capacity: int):
        self.items = []  # 数组
        self.capacity = capacity  # 数组长度
        self.head = 0  # 队列第一个数据下标
        self.tail = 0  # 队列最后一个数据下标

    def enqueue(self, item: str) -> bool:
        if (self.tail + 1) % self.capacity == self.head:
            return False

        self.items.append(item)
        self.tail = (self.tail + 1) % self.capacity
        return True

    def dequeue(self) -> Optional[str]:
        if self.head != self.tail:
            item = self.items[self.head]
            self.head = (self.head + 1) % self.capacity
            return item

    def __repr__(self) -> str:
        if self.tail >= self.head:
            return "->".join(item for item in self.items[self.head: self.tail])
        else:
            return "->".join(item for item in chain(self.items[self.head:], self.items[:self.tail]))


if __name__ == '__main__':
    queue = LinkedQueue()
    for i in range(10):
        queue.enqueue(str(i))
    print(queue)
    queue.dequeue()
    print(queue)
    q = CircularQueue(5)
    for i in range(5):
        q.enqueue(str(i))
    print(q)
    q.dequeue()
    print(q)
